﻿// Copyright (C) Jari Hautio <jari.hautio@iki.fi> 2009. Licensed under GPLv2. See LICENSE.txt in solution folder.
using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace ColorLib
{
    // Selects color so that squared error distance in target image will be
    // minimized
    public class MinErrorPicker
    {
        Dictionary<Color, int> colors = new Dictionary<Color, int>();
        
        public Dictionary<Color, int> Colors
        {
            get { return colors; }
            set { colors = value; Init(); }
        }

        struct ColorItem
        {
            public Color c; // the color
            public int n; // pixel count
            public double e; // error value to best picked color
            public int s; // sequence number(picked colors), when error value was updated
        }
        SortedList<double, LinkedList<ColorItem>> unpicked = new SortedList<double,LinkedList<ColorItem>>();
        List<Color> picked = new List<Color>();
		public int PickedCount { get { return picked.Count;}}

        public double CalcDistance2(Color c1, Color c2)
        {
            return 0.25 * (ColorLib.ColorMath.DistanceYCbCrFast(c1, c2)) +
                    0.25 * ((c1.R - c2.R) * (c1.R - c2.R) + (c1.G - c2.G) * (c1.G - c2.G) + (c1.B - c2.B) * (c1.B - c2.B));
        }
        double CalculateError(ColorItem colorItem, Color targetColor)
        {
            return colorItem.n * CalcDistance2(colorItem.c, targetColor);
        }
        double UpdateError(ref ColorItem ci)
        {
            ci.e = ci.n*3*255*255;
            // find best match/smallest error in picked colors
            double best = double.MaxValue;
            foreach (Color p in picked)
            {
                double e = CalculateError(ci, p);
                if (e < best)
                    best = e;
            }
            ci.s = picked.Count;
            if (ci.s > 0)
                ci.e = best;
            return ci.e;
        }
        void AddToUnpicked(ColorItem ci)
        {
            double k = UpdateError(ref ci);
            if (unpicked.ContainsKey(k))
                unpicked[k].AddLast(ci);
            else
            {
                LinkedList<ColorItem> l = new LinkedList<ColorItem>();
                l.AddFirst(ci);
                unpicked.Add(k, l);
            }
        }
        public void Init()
        {
            picked.Clear();
            Color c = Color.Empty;
            int n =0;
            foreach (KeyValuePair<Color, int> t in colors)
            {
                if (n < t.Value)
                {
                    n = t.Value;
                    c = t.Key;
                }
            }
            picked.Add(c);
            foreach (KeyValuePair<Color, int> t in colors)
            {
                if (t.Key == c) continue;
                ColorItem ci = new ColorItem();
                ci.c = t.Key;
                ci.n = t.Value;
                AddToUnpicked(ci);
            }
        }

        // Make sure se have this many colors selected
        // and return selected colors
        public List<Color> Select(int n)
        {
            for (int i=picked.Count; i < n; i++)
            {
                SelectOne();
            }
            /*
            List<Color> r = new List<Color>();
            for (int i = 0; i < n; i++)
                r.Add(picked[n]);
             * */
            return picked;
        }
        public Color SelectOne()
        {
            if (unpicked.Count == 0) return Color.Empty;

            int seq = picked.Count;

            while (unpicked.Count > 0)
            {
                int i = unpicked.Count - 1;
                while (i>=0 && unpicked.Values[i].Count == 0)
                {
                    unpicked.RemoveAt(i);
                    i--;
                }
                if (unpicked.Count == 0) break;
                LinkedList<ColorItem> last = unpicked.Values[i];
                ColorItem ci = last.First.Value;
                last.RemoveFirst();
                if (last.Count == 0)
                    unpicked.RemoveAt(i);
                // check if it is outdated, 
                // if so then update it and restart search
                if (ci.s < seq)
                {
                    AddToUnpicked(ci);
                    continue;
                }
                picked.Add(ci.c);
                return ci.c;
            }

            return Color.Empty;
        }
    }
}
